package com.zghhost.codedemo.util;

import java.util.Arrays;

/**
 * @author guohua.zhang@zhaopin.com.cn
 * @Date 2019/5/27 16:59
 */
public class SortUtils {
    /**
     * 冒泡排序
     * 时间复杂度 最好 O(n) 最坏 O(N^2)
     * 空间复杂度 O(1)
     * 稳定
     */
    public static void bubbleSort(int[] is){
        for(int i=0,ic=is.length;i<ic;i++){
            for(int j=i+1;j<ic;j++){
                if(is[i] > is[j]){
                    int temp = is[j];
                    is[j] = is[i];
                    is[i] = temp;
                    System.out.println(Arrays.toString(is));
                }
            }
        }
    }

    /**
     * 选择排序
     * 时间负责度 O(N^2)
     * 空间负责度 O(1)
     * 不稳定
     * 对比冒泡排序：比较次数相同，交换次数更少
     */
    public static void selectionSort(int[] is){
        for(int i=0,ic=is.length;i<ic;i++){
            int minIndex = i;
            for(int j=i+1,jc=is.length;j<jc;j++){
                if(is[j] < is[minIndex]){
                    minIndex = j;
                }
            }
            if(minIndex != i){
                int temp = is[i];
                is[i] = is[minIndex];
                is[minIndex] = temp;
            }
        }
    }

    /**
     * 插入排序
     * 时间复杂度 最好 O(N) 最坏 O(N^2)
     * 空间复杂度 O(1)
     * 稳定
     * 对比冒泡和选择：对比选择可能出现O(N)，对比冒泡移动次数少
     */
    public static void insertionSort(int[] is){
        if(is.length < 1){
            return;
        }


        int current;

        //方式1
//        for(int i=0,ic=is.length;i<ic-1;i++){
//            current = is[i+1];
//            int index = i;
//            for(;index >= 0 && current < is[index];index--){
//                is[index+1] = is[index];
//            }
//            is[index+1] = current;
//        }

        //方式2
        for(int i=1,ic=is.length;i<ic;i++){
            current = is[i];
            int index = i-1;
            for(;index >= 0 && current < is[index];index--){
                is[index+1] = is[index];
                System.out.println(Arrays.toString(is));
            }
            is[index+1] = current;
        }
    }

    /**
     * O(n log n)
     * 空间复杂度 O(n)
     * 最佳情况：T(n) = O(n)  最差情况：T(n) = O(nlogn)  平均情况：T(n) = O(nlogn)
     * 数组外完成
     */
    public static int[] mergeSort(int[] is){
        if(is.length < 2){
            return is;
        }
        int mid = is.length/2;
        int[] left = Arrays.copyOfRange(is,0,mid);
        int[] right = Arrays.copyOfRange(is,mid,is.length);
        return merge(mergeSort(left),mergeSort(right));
    }

    public static int[] merge(int[] left,int[] right){
        int[] result = new int[left.length+right.length];
        for(int ri=0,i=0,j=0;ri<result.length;ri++){
            if(i >= left.length){
                result[ri] = right[j];
                j++;
            }else if(j >= right.length){
                result[ri] = left[i];
                i++;
            }else if(left[i] < right[j]){
                result[ri] = left[i];
                i++;
            }else{
                result[ri] = right[j];
                j++;
            }
        }
        return result;
    }


    /**
     * 快速排序
     * 时间：O(n log n) 最坏 O(n^2)
     * 空间：O(log n)
     * 不稳定
     * 数组内完成
     */
    public static void quickSort(int[] is){
        if(is.length <= 1){
            return;
        }
        quickSort(is,0,is.length-1);
    }

    public static void quickSort(int[] is,int li,int ri){
        if(is.length <= 1){
            return;
        }
        if(li < ri){
            int pindex = partition(is,li,ri);
            quickSort(is,li,pindex-1);
            quickSort(is,pindex+1,ri);
        }
    }

    public static int partition(int[] is,int li,int ri){
        int pivot = li,index=pivot+1;
        for(int i=index;i<=ri;i++){
            if(is[i] < is[pivot]){
                swap(is,i,index);
                index++;
            }
        }
        swap(is,pivot,index-1);
        return index - 1;
    }


    public static void swap(int[] is,int i,int j){
        int tmp = is[j];
        is[j] = is[i];
        is[i] = tmp;
    }

    public static void main(String[] args)throws Exception{
        int[] is = new int[]{64,12,34,73,13,83,1,46,30,10,30,102,43};
//        SortUtils.bubbleSort(is);
//        System.out.println("-----------");
//        SortUtils.selectionSort(is);
//        SortUtils.insertionSort(is);
        SortUtils.quickSort(is);
        System.out.println(Arrays.toString(is));
    }
}
